package doing.normal_901_1000;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 987. Vertical Order Traversal of a Binary Tree 二叉树的垂序遍历
 * <p>
 * 给定二叉树，按垂序遍历返回其结点值。
 * 对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
 * 把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，
 * 我们按从上到下的顺序报告结点的值（ Y 坐标递减）。
 * 如果两个结点位置相同，则首先报告的结点值较小。
 * 按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
 * <p>
 * 示例 1：
 * 3
 * /   \
 * 9    20
 * /   \
 * 15    7
 * <p>
 * 输入：[3, 9, 20, null, null, 15, 7]
 * 输出：[[9],
 * [3,15],
 * [20],
 * [7]]
 * 解释：
 * 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：
 * 然后，值为 9 的结点出现在 (-1, -1)；
 * 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；
 * 值为 20 的结点出现在 (1, -1)；
 * 值为 7 的结点出现在 (2, -2)。
 * <p>
 * 2019-05-12 18:27
 **/
@SuppressWarnings("all")
public class VerticalOrderTraversalOfABinaryTree {

    ArrayList<Pointer> list = new ArrayList<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        Collections.sort(list, new Comparator<Pointer>() {
            @Override
            public int compare(Pointer p1, Pointer p2) {
                //x, y, val
                if (p1.x != p2.x) return Integer.compare(p1.x, p2.x);
                if (p1.y != p2.y) return Integer.compare(p2.y, p1.y);
                return Integer.compare(p1.val, p2.val);
            }
        });

        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>();
        int x = 0, i = -1;
        for (Pointer p : list) {
            if (i == -1 || p.x != x) {
                ArrayList<Integer> newList = new ArrayList<Integer>();
                newList.add(p.val);
                ans.add(newList);
                i++;
                x = p.x;
            } else {
                ans.get(i).add(p.val);
            }
        }
        return ans;
    }

    public void dfs(TreeNode root, int x, int y) {
        if (root != null) {
            list.add(new Pointer(x, y, root.val));
            dfs(root.left, x - 1, y - 1);
            dfs(root.right, x + 1, y - 1);
        }
    }

    class Pointer {
        public int x;
        public int y;
        public int val;

        public Pointer(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    }

    @Test
    public void test() {
        info(verticalTraversal(new TreeNode(3, 9, new TreeNode(20, 15, 7))));
    }
}





































/*
ArrayList<Pointer> list = new ArrayList<Pointer>();

public List<List<Integer>> verticalTraversal(TreeNode root) {
    dfs(root, 0, 0);
    Collections.sort(list, new Comparator<Pointer>() {
        @Override
        public int compare(Pointer p1, Pointer p2) {
            //x, y, val
            if(p1.x != p2.x) return Integer.compare(p1.x, p2.x);
            if(p1.y != p2.y) return Integer.compare(p2.y, p1.y);
            return Integer.compare(p1.val, p2.val);
        }
    });
    ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>();
    int x = 0, i = -1;
    for(Pointer p : list){
        if(i == -1 || p.x != x){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            newList.add(p.val);
            ans.add(newList);
            i++;
            x = p.x;
        }else{
            ans.get(i).add(p.val);
        }
    }
    return ans;
}

public void dfs(TreeNode root, int x, int y){
    if(root != null){
        list.add(new Pointer(x, y, root.val));
        dfs(root.left, x-1, y-1);
        dfs(root.right, x+1, y-1);
    }
}

class Pointer{
public int x;
public int y;
public int val;

public Pointer(int x, int y, int val){
    this.x = x;
    this.y = y;
    this.val = val;
}
}
*/
